DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2022.56

Disjointness Graphs of Short Polygonal Chains

Authors: János Pach, Gábor Tardos, and Géza Tóth

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract

The disjointness graph of a set system is a graph whose vertices are the sets, two being connected by an edge if and only if they are disjoint. It is known that the disjointness graph G of any system of segments in the plane is χ-bounded, that is, its chromatic number χ(G) is upper bounded by a function of its clique number ω(G). Here we show that this statement does not remain true for systems of polygonal chains of length 2. We also construct systems of polygonal chains of length 3 such that their disjointness graphs have arbitrarily large girth and chromatic number. In the opposite direction, we show that the class of disjointness graphs of (possibly self-intersecting) 2-way infinite polygonal chains of length 3 is χ-bounded: for every such graph G, we have χ(G) ≤ (ω(G))³+ω(G).

Cite as

János Pach, Gábor Tardos, and Géza Tóth. Disjointness Graphs of Short Polygonal Chains. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 56:1-56:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{pach_et_al:LIPIcs.SoCG.2022.56,
  author =	{Pach, J\'{a}nos and Tardos, G\'{a}bor and T\'{o}th, G\'{e}za},
  title =	{{Disjointness Graphs of Short Polygonal Chains}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{56:1--56:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.56},
  URN =		{urn:nbn:de:0030-drops-160645},
  doi =		{10.4230/LIPIcs.SoCG.2022.56},
  annote =	{Keywords: chi-bounded, disjointness graph}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2017.59

Disjointness Graphs of Segments

Authors: János Pach, Gábor Tardos, and Géza Tóth

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract

The disjointness graph G=G(S) of a set of segments S in R^d, d>1 is a graph whose vertex set is S and two vertices are connected by an edge if and only if the corresponding segments are disjoint. We prove that the chromatic number of G satisfies chi(G)<=omega(G)^4+omega(G)^3 where omega(G) denotes the clique number of G. It follows, that S has at least cn^{1/5} pairwise intersecting or pairwise disjoint elements. Stronger bounds are established for lines in space, instead of segments. We show that computing omega(G) and chi(G) for disjointness graphs of lines in space are NP-hard tasks. However, we can design efficient algorithms to compute proper colorings of G in which the number of colors satisfies the above upper bounds. One cannot expect similar results for sets of continuous arcs, instead of segments, even in the plane. We construct families of arcs whose disjointness graphs are triangle-free (omega(G)=2), but whose chromatic numbers are arbitrarily large.

Cite as

János Pach, Gábor Tardos, and Géza Tóth. Disjointness Graphs of Segments. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 59:1-59:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{pach_et_al:LIPIcs.SoCG.2017.59,
  author =	{Pach, J\'{a}nos and Tardos, G\'{a}bor and T\'{o}th, G\'{e}za},
  title =	{{Disjointness Graphs of Segments}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{59:1--59:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.59},
  URN =		{urn:nbn:de:0030-drops-71960},
  doi =		{10.4230/LIPIcs.SoCG.2017.59},
  annote =	{Keywords: disjointness graph, chromatic number, clique number, chi-bounded}
}

Search Results

Documents authored by Tardos, Gábor

Disjointness Graphs of Short Polygonal Chains

Abstract

Cite as

Disjointness Graphs of Segments

Abstract

Cite as

Thanks for your feedback!

Could not send message